package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/14.<br><br>
 *
 * 两个数组的交集
 */
public class Topic349 {
    public static void main(String[] args) {
        Topic349 instance = new Topic349();

        int[] array1 = new int[] {1,2,2,1};
        int[] array2 = new int[] {2,2};
        Util.printArray(instance.intersection(array1, array2));

        array1 = new int[] {4,9,5};
        array2 = new int[] {9,4,9,8,4};
        Util.printArray(instance.intersection(array1, array2));
    }

    public int[] intersection(int[] nums1, int[] nums2) {
        boolean[] array = new boolean[1001];

        for(int value : nums1) {
            array[value] = true;
        }

        int[] result = new int[Math.min(nums1.length, nums2.length)];
        int index = 0;
        for(int value : nums2) {
            if(array[value]) {
                result[index++] = value;
                array[value] = false;
            }
        }

        return Arrays.copyOf(result, index);
    }

    public int[] intersection2(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();

        for(int value : nums1) {
            set1.add(value);
        }

        for(int value : nums2) {
            if(set1.contains(value)) {
                set2.add(value);
            }
        }

        int[] result = new int[set2.size()];
        int index = 0;
        for(int value : set2) {
            result[index++] = value;
        }

        return result;
    }
}
